using System;
using System.Collections.Generic;
using CLELCore.Assembly.CLELInstructions;
using opt.Analysis.Graph;

namespace opt.Analysis.Graph.ControlFlowGraph
{
	public class ControlFlowGraph<T,U> : Graph<T,U> where U : CFGNodeInfo,new()
						where T : CFGArcInfo,new()
	{
		List<CLELInstruction> _code;

		public ControlFlowGraph(List<CLELInstruction> code)
		{
			if(code == null)
				throw new ArgumentException("Code cannot be null");
			_code = code;
			BuildControlFlowGraph();
		}

		private void BuildControlFlowGraph()
		{
			int code_count = _code.Count;
			int i;
			bool [] first = new bool[code_count];
			CLELInstruction inst;
			int current_offset = 0;
			Dictionary<int,int> all_offsets = new Dictionary<int,int>();
			Dictionary<int,int> all_indexes = new Dictionary<int,int>();
			for(i = 0;i < code_count;i++)
			{
				first[i] = false;
				inst = _code[i];
				all_offsets.Add(current_offset,i);
				all_indexes.Add(i,current_offset);
				current_offset += inst.Length;
			}
		
			byte opcode;
			int offset;
			int br_target;
			int br_target_index;
			current_offset = 0;
			first[0] = true; //mark first instruction
			for(i = 0;i < code_count;i++)
			{
				inst = _code[i];
				opcode = inst.Opcode;
				if(opcode == CLELOpcode.RET)
				{
					first[i] = true;
				}
				else
				{
					offset = 0;
					if(BranchUtilities.GetBranchOffset(inst,ref offset))
					{
						br_target = current_offset+inst.Length+offset;
						br_target_index = all_offsets[br_target];
						first[br_target_index] = true;  //mark destination of branch
						if(i+1 < code_count)
							first[i+1] = true;   //mark instruction after branch
					}
				}
				current_offset += inst.Length;
			}

			//create all nodes
			int last;
			U u;
			List<GraphNode<T,U>> nodes = new List<GraphNode<T,U>>();
			GraphNode<T,U> node;
			for(i = 0;i < code_count;i++)
			{
				if(first[i])
				{
					//Console.WriteLine(i);
					last = getLastInstruction(first,i);
					u = new U();
					u.Code = _code.GetRange(i,last-i+1);
					u.StartInstructionIndex = i;
					
					node = new GraphNode<T,U>();
					node.Data = u;
					nodes.Add(node);	
				}
			}

			//add arcs
			int nodes_count = nodes.Count;
			GraphNode<T,U> to;
			int inst_index;
			bool [] seen = new bool[nodes_count];
			for(i = 0;i < nodes_count;i++)
				seen[i] = false;

			for(i = 0;i < nodes_count;i++)
			{
				node = nodes[i];
				inst = node.Data.Code[node.Data.CodeCount-1];
				inst_index = node.Data.StartInstructionIndex+node.Data.CodeCount-1;
				offset = 0;
				if(BranchUtilities.GetBranchOffset(inst,ref offset))
				{
					current_offset = all_indexes[inst_index];
					br_target = current_offset+inst.Length+offset;
					br_target_index = all_offsets[br_target];
					to = GetNodeAtTarget(nodes,br_target_index,seen);
					if(to != null)
					{
						//make arc from when the branch is taken
						node.AddGraphArc(new GraphArc<T,U>(to,new T()));
						to.AddBackGraphArc(new GraphArc<T,U>(node,null));
						
						//if conditional branch, add fall through arc
						if(BranchUtilities.IsConditionalBranch(inst))
						{
							//if there is a next node
							if(i+1 < nodes_count)
							{
								node.AddGraphArc(new GraphArc<T,U>(nodes[i+1],new T()));
								nodes[i+1].AddBackGraphArc(new GraphArc<T,U>(node,null));
								seen[i+1] = true;
							}
						}
					}
				}
				else
				{
					//if there is a next node
					if(i+1 < nodes_count)
					{
						node.AddGraphArc(new GraphArc<T,U>(nodes[i+1],new T()));
						nodes[i+1].AddBackGraphArc(new GraphArc<T,U>(node,null));
						seen[i+1] = true;
					}
				}
			}

			for(i = 0;i < nodes_count;i++)
			{
				if(!seen[i])
				{
					_graph_roots.Add(nodes[i]);
				}
			}
		}

		private GraphNode<T,U> GetNodeAtTarget(List<GraphNode<T,U>> nodes,int index,bool [] seen)
		{
			int nodes_count = nodes.Count;
			int i;
			int start,end;
			for(i = 0;i < nodes_count;i++)
			{
				start = nodes[i].Data.StartInstructionIndex;
				end = start+nodes[i].Data.CodeCount;
				if(index >= start && index < end)
				{
					seen[i] = true;
					return nodes[i];
				}
			}
			return null;
		}

		private int getLastInstruction(bool [] first,int index)
		{
			int i;
			int first_count = first.Length;
			for(i = index+1;i < first_count;i++)
				if(first[i])
					return i-1;
			return first_count-1;
		}
	
		/*	
		public static void print(List<CLELInstruction> code)
		{
			Console.WriteLine("Start");
			int i;
			CLELInstruction inst;
			int offset = 0;
			for(i = 0;i < code.Count;i++)
			{
				inst = code[i];
				Console.WriteLine(offset+": "+inst);
				offset += inst.Length;
			}
		}
		*/
	}
}
